The present invention relates to integrated circuits, and more particularly to a method of identifying a multiplexer in a combinational logic.
Multiplexers and related logic are common types of combinational logic in digital circuits. FIGS. 1A, 1B and 1C respectively show a multiplexer 10, a selector 20 and a decoder 30. The binary multiplexer (mux) 10 is shown as having n data inputs (n>0) d[n−1 . . . 0] and m select inputs s[m−1 . . . 0], where n=2m. A mux with n data inputs is also called an n:1 mux. The output O is set to d[i], where i is the decimal number represented by the binary number s[m−1 . . . 0]. So for n=4, O=s[0]′s[1]′d[0]+s[0]s[1]′d[1]+s[0]′s[1]d[2]+s[0]s[1]d[3], where notation “′” represent an inverse of a signal.
A selector, such as selector 20, has n data inputs d[n−1 . . . 0] and n select inputs s[n−1 . . . 0] (n>0). The select signals are one-hot, i.e., at any point in time only one of the select signals is at a high level 1. The output O is set to d[i] when s[i]=1. So for n=4, O=s[0]d[0]+s[1]d[1]+s[2]d[2]+s[3]d[3].
A decoder, such as decoder 30, has n inputs in[n−1 . . . 0] and m outputs o[m−1 . . . 0], where n>0, m>0, and m=2n. For each i, O[i] is 1 if in[n−1 . . . 0] is the binary representation of decimal number i, and 0 otherwise. So for, e.g., n=4, O[0]=in[0]′in[1]′, O[1]=in[0]in[1]′, O[2]=in[0]′in[1], and O[3]=in[0]in[1].
One or more of the data signals received by selector 20 and mux 10 may be constant. The select signals applied to mux 10 and selector 20 and the input signals on the decoder 30 are assumed to be non-constant and unique. If this is not the case, the mux or selector can be reduced to a smaller size mux or selector that has only non-constant and unique select signals.
The output of a decoder may drive the select inputs of a selector providing the same functionality as a n:1 mux, where n is the data width of the decoder and the selector. The inputs of the decoder represent the select inputs of the mux, and the data inputs of the selector represent the data inputs of the mux. During synthesis of a logic code, written for example in VHDL or Verilog, these decoder-selector pairs are desired to replaced by an equivalent n:1 mux.
An HDL code for a mux may be written in a number of different ways. Tables I and II below are two different Verilog codes for a 16:1 mux. The code in Table II is usually used when the different data signals come from different variables, and not from one bus.
TABLE Imodule mux_test(d,s,o);input [NUM_DATA-1:0] d;input [NUM_SEL-1:0] s;output o;reg o;parameter NUM_DATA=16;parameter NUM_SEL=4;always@(d or s)begino = d[s];endendmodule
TABLE IImodule mux_test(d,s,o);input [NUM_DATA-1:0] d;input [NUM_SEL-1:0] s;output o;reg o;parameter NUM_DATA=16;parameter NUM_SEL=4;always@(d or s)begincase (s)4′b0000 :o = d[0];4′b0001 :o = d[1];4′b0010 :o = d[2];4′b0011 :o = d[3];4′b0100 :o = d[4];4′b0101 :o = d[5];4′b0110 :o = d[6];4′b0111 :o = d[7];4′b1000 :o = d[8];4′b1001 :o = d[9];4′b1010 :o = d[10];4′b1011 :o = d[11];4′b1100 :o = d[12];4′b1101 :o = d[13];4′b1110 :o = d[14];4′b1111 :o = d[15];endcaseendendmodule
Another known Verilog code for a decoder driving a selector and specifying an n:1 mux is shown, in part, in Table III below. Each variable “deci” is an output of the decoder. The selector is defined by a sequence of “if . . . else if” statement, although the selector cannot be readily seen from this sequence. Extraction generates a chain of 2:1 muxes 401, 402 . . . 40N for this code, as shown in FIG. 2.
TABLE IIImodule mux test(d,s,o);input [NUM_DATA-1:0] d;input [NUM_SEL-1:0] s;output o;reg o;reg dec0;...reg dec15;parameter NUM_DATA=16;parameter NUM_SEL=4;always@(d or s)begindec0=1′b0;...dec15=1′b0;case (s)4′b0000 :dec0 = 1′b1;4′b0001 :dec1 = 1′b1;4′b0010 :dec2 = 1′b1;...4′b1111 :dec15 = 1′b1;endcaseif (dec0 == 1′b1)o = d[0];else if (dec1 == 1′b1)o = d[1];else if (dec2 == 1′b1)o = d[2];else if (dec3 == 1′b1)o =d[3];...else if (dec14 == 1′b1)o = d[14];else if (dec15 == 1′b1)o = d[15];elseo = 1′b0;endendmodule
From the decoder, it can be seen that the conditions in the “if . . . else if” chain are disjoint, i.e. they can never be high at the same time. Accordingly, the “if . . . else if” chain can be transformed into a selector. The decoder-selector pair can thus be replaced by an n:1 mux.
The process of transformation is more complicated if the decoder is not defined in a clear manner. For instance, in Table IV below, the decoder is only enabled when variable “ena” is true, thus posing difficulties for the extractor to recognize the decoder. This indicates that the select inputs of the chain of muxes 401, 402 . . . 40N are driven by an arbitrary logic block 42, as shown in FIG. 3. It can be seen however, that the logic is equivalent to an n:1 mux 46 driving a 2:1 mux 48, as shown in FIG. 4. Even more challenging are conditions in which only a subset of select signals generate different data. This means that the different decoder outputs are lumped together, rendering the logic block even more arbitrary.
TABLE IVmodule mux_test(d,s,o,ena);input [NUM_DATA-1:0] d;input [NUM_SEL-1:0] s;input enaoutput o;reg o;reg dec0;...reg dec15;parameter NUM_DATA=16;parameter NUM_SEL=4;always@(d or s or ena)begindec0=1′b0;...dec15=1′b0;case (s)4′b0000 :dec0 = ena & 1′b1;4′b0001 :dec1 = ena & 1′b1;...4′b1111 :dec15 = ena & 1′b1;endcaseif (dec0 == 1′b1)o = d[0];else if (dec1 == 1′b1);o = d[1];else if (dec2 == 1′b1)o = d[2];...else if (dec15 == 1′b1)o = d[15];elseo = 1′b0;endendmodule